
LLVM代码生成器将LLVM IR中的一个模块作为输入，并将其转换为目标代码或汇编文本，需要将AST表示转换为IR。为了实现一个IR代码生成器，首先看一个简单的例子，然后开发代码生成器所需的类。完整的实现将分为三类:

\begin{itemize}
\item
CodeGenerator

\item
CGModule

\item
CGProcedure
\end{itemize}

CodeGenerator类是编译器驱动程序使用的通用接口，CGModule和CGProcedure类保存为编译单元和单个函数生成IR代码所需的状态。

我们将从clang生成的IR开始。

\mySubsubsection{4.1.1.}{理解IR代码}

生成IR代码之前，最好先了解一下IR语言的主要元素。在第2章中，简要介绍了IR。获得更多IR知识的一个简单方法是研究clang的输出。例如，这个C代码(gcd.c)，其实现了计算两个数的最大公约数的欧几里得算法:

\begin{cpp}
unsigned gcd(unsigned a, unsigned b) {
    if (b == 0)
    return a;
    while (b != 0) {
        unsigned t = a % b;
        a = b;
        b = t;
    }
    return a;
}
\end{cpp}

使用clang创建IR文件(gcd.ll):

\begin{shell}
$ clang --target=aarch64-linux-gnu -O1 -S -emit-llvm gcd.c
\end{shell}

IR代码与目标有关，说明该命令用于编译Linux下ARM 64位CPU的源文件。-S选项指示clang输出一个程序集文件，通过设置-emit-llvm选项，创建一个IR文件。优化级别-O1，用于获得一个易于阅读的IR代码。Clang有更多的选项，所有这些选项都在\url{https://clang.llvm.org/docs/ClangCommandLineReference.html}的命令行参数引用中进行了记录。来看一下生成的文件，并理解C代码是如何映射到LLVM IR的。

一个C文件翻译成一个模块，其中包含函数和数据对象。一个函数至少有一个基本块，一个基本块包含指令，这种分层结构也反映在C++ API中。所有数据元素都有类型，整数类型由字母i和位数表示。例如，64位整数类型写为i64。最基本的浮点类型是float和double，分别表示32位和64位IEEE浮点类型。也可以创建聚合类型，如vector、数组和结构体。

以下是LLVM IR，在文件的顶部，确定了一些基本属性。

\begin{shell}
; ModuleID = 'gcd.c'
source_filename = "gcd.c"
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-
n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"
\end{shell}

第一行是一个注释，表面使用了哪个模块标识符。下一行中，将命名源文件的文件名。对于clang，两者一样。

目标数据布局字符串建立一些基本属性。不同的部分用-号隔开。包括以下信息:

\begin{itemize}
\item
小写e表示内存中的字节使用小端模式存储。要指定大端序，必须使用大写E。

\item
M: 指定应用于符号的名称改写。这里，m:e表示使用ELF名称改写。

\item
iN:A:P形式，例如i8:8:32，指定了数据的对齐方式，以位表示。第一个数字是ABI要求的对齐方式，第二个数字是首选对齐方式。对于字节(i8)， ABI对齐是1字节(8)，首选对齐是4字节(32)。

\item
n指定可用的本机寄存器大小，n32:64表示原生支持32位和64位宽的整数。

\item
S指定了栈的对齐方式，同样以位为单位。S128表示栈保持16字节对齐。
\end{itemize}

\begin{myNotic}{Note}
所提供的目标数据布局必须与后端期望的匹配，将捕获的信息传递给与目标无关的优化过程。例如，优化过程可以查询数据布局以获得指针的大小和对齐方式，但改变数据布局中指针的大小，并不会改变后端代码的生成。

目标数据布局提供了更多的信息，可以在\url{https://llvm.org/docs/LangRef.html#data-layout}的参考手册中找到更多信息。
\end{myNotic}

最后，目标三重字符串指定了我们要编译的架构，在命令行上给出的信息。三元组是一个配置字符串，通常由CPU架构、厂商和操作系统组成，通常还会添加更多关于环境的信息。例如，x86\_64-pc-win32三元组用于运行在64位x86 CPU上的Windows系统。x86\_64是CPU架构，pc是通用的供应商，win32是操作系统。各部分用连字符连接。在ARMv8 CPU上运行的Linux系统使用aarch64-unknown-linux-gnu作为它的三元组。aarch64是CPU架构，而操作系统是运行gnu环境的linux。基于linux的系统没有真正的供应商，所以这部分未知。对于特定目的而言，不知道或不重要的部分通常忽略:所以aarch64-linux-gnu和aarch64-unknown-linux-gnu三元组描述了同一个Linux系统。

接下来，在IR文件中定义gcd函数:

\begin{shell}
define i32 @gcd(i32 %a, i32 %b) {
\end{shell}

这类似于C文件中的函数签名。无符号数据类型被转换成32位整数类型i32。函数名以@为前缀，参数名以\%为前缀。函数体用大括号括起来:

\begin{shell}
entry:
    %cmp = icmp eq i32 %b, 0
    br i1 %cmp, label %return, label %while.body
\end{shell}

IR代码组织成基本块，格式良好的基本块是一个线性指令序列，以一个可选的标签开始，以一个终止指令结束，所以每个基本块都有一个入口点和一个出口点。LLVM允许在构造时使用畸形基本块，第一个基本块的标签是entry。代码块中的代码很简单:第一条指令将\%b参数与0进行比较。第二条指令在条件为true时跳转到return标签，然后跳转到while语句。若条件为false，则使用body标签。

IR代码的另一个特点是采用静态单一赋值(SSA)形式。代码使用无限量的虚拟寄存器，但每个寄存器只写入一次。比较的结果会赋值给指定的虚拟寄存器\%cmp，使用这个寄存器，但不再写入。诸如常量传播和公共子表达式消除之类的优化，在SSA形式下工作得非常好，所有现代编译器都在使用。

\begin{myTip}{SSA}
SSA是在20世纪80年代后期发展起来的，因其简化了数据流分析和优化，所以广泛应用于编译器中。例如，R是SSA形式，循环内部公共子表达式的识别就会容易得多。SSA的一个基本属性是建立了def-use和use-def链:对于单个定义，可知道所有的用法(def-use)，对于每个用法，知道唯一的定义(use-def)。这个信息广泛使用，例如在常量传播中:若一个定义确定为常量，则所有对该值的使用都可以很容易地替换为该常量值。

Cytron等人(1989)提出的构造SSA形式的算法非常流行，也用于LLVM的实现。早期的观察发现，若语言没有goto语句，这些算法会变得更简单。

对SSA的深入研究可以在F. rastello和F. B. Tichadou的《基于SSA的编译器设计》一书中找到，Springer 2022。
\end{myTip}

下一个基本块是while循环的主体:

\begin{shell}
while.body:
    %b.loop = phi i32 [ %rem, %while.body ],
                        [ %b, %entry ]
    %a.loop = phi i32 [ %b.loop, %while.body ],
                        [ %a, %entry ]
    %rem = urem i32 %a.loop, %b.loop
    %cmp1 = icmp eq i32 %rem, 0
    br i1 %cmp1, label %return, label %while.body
\end{shell}

在gcd的循环中，参数a和b会赋新值。若一个寄存器只能写入一次，则是不可能的。解决方案是使用特殊的phi指令，phi指令有一个基本块和值的列表作为参数。基本块表示来自该基本块的传入边，值是来自该基本块的值。运行时，phi指令将之前执行的基本块的标签与参数列表中的标签进行比较。

指令的值就是与标签相关联的值。对于第一条phi指令，若先前执行的基本块是while.body，则该值为\%rem寄存器。若先前执行的基本块，则值为\%b，这些值是位于基本块开头的值。\%b循环寄存器从第一个phi指令获取一个值。第二个phi指令的参数列表中使用了相同的寄存器，但假定该值是通过第一个phi指令改变之前的值。

循环体之后，必须选择返回值:

\begin{shell}
return:
    %retval = phi i32 [ %a, %entry ],
                      [ %b.loop, %while.body ]
    ret i32 %retval
}
\end{shell}

同样，phi指令用于选择所需的值。ret指令不仅结束了这个基本块，运行时表示这个函数的结束。它有一个返回值作为参数。

使用phi指令有一些限制，必须是基本块的第一个指令。第一个基本块比较特殊:没有之前执行过的块，所以不能以phi指令开始。

\begin{myTip}{LLVM IR参考}
我们只触及了LLVM IR的皮毛，访问LLVM语言参考手册\url{https://llvm.org/docs/LangRef.html}，可了解更多细节。
\end{myTip}

IR代码本身看起来很像C语言和汇编语言的混合体。尽管有这种熟悉的风格，但还是不清楚如何使用AST生成IR代码，尤其是phi指令看起来很难生成。下一节中，将为此实现一个算法!

\mySubsubsection{4.1.2.}{了解加载和存储的方法}

LLVM中的所有局部优化都是基于这里所示的SSA，使用全局变量的内存引用。IR语言有load和store指令，用于获取和存储这些值，也可以将此用于局部变量。这些指令不属于SSA形式，LLVM知道如何将其转换为所需的SSA，可以为每个局部变量分配内存槽，并使用load和store指令来更改它们的值，只需要记住指向存储变量的内存槽的指针。clang编译器使用这种方法。

来看一下load和store的IR代码。再次编译gcd.c，但这次没有启用优化:

\begin{shell}
$ clang --target=aarch64-linux-gnu -S -emit-llvm gcd.c
\end{shell}

gcd函数现在看起来有所不同。这是第一个基本块:

\begin{shell}
define i32 @gcd(i32, i32) {
    %3 = alloca i32, align 4
    %4 = alloca i32, align 4
    %5 = alloca i32, align 4
    %6 = alloca i32, align 4
    store i32 %0, ptr %4, align 4
    store i32 %1, ptr %5, align 4
    %7 = load i32, ptr %5, align 4
    %8 = icmp eq i32 %7, 0
    br i1 %8, label %9, label %11
\end{shell}

IR代码现在依赖于寄存器和标签的自动编号，未指定参数的名称，隐式地为\%0和\%1。基本块没有标签，因此赋值为2，前几条指令为4个32位值分配内存。之后，参数\%0和\%1存储在寄存器\%4和\%5指向的内存槽中。为了比较\%1和0，这个值显式地从内存槽加载。使用这种方法，不需要使用phi指令!相反，可以从内存槽中加载一个值进行计算，然后将新值存储回内存槽中。下次读取内存槽时，就会得到最后一次计算的值。gcd函数的所有其他基本块都遵循这种模式。

以这种方式使用加载和存储指令的优点是，生成IR代码相当容易；缺点是，在将基本块转换为SSA形式后，在第一个优化步骤中，LLVM将使用mem2reg时，会删除大量的IR指令。

因此，我们直接生成SSA形式的IR代码，通过将控制流映射到基本块开始生成IR代码。

\mySubsubsection{4.1.3.}{控制流映射到基本块}

基本块的概念，是按该顺序执行的指令的线性序列。基本块在开始时只有一个条目，以终止指令结束，终止指令是将控制流转移到另一个基本块的指令，例如：分支指令、切换指令或返回指令。请参阅\url{https://llvm.org/docs/LangRef.html#terminator-instructions}获取终止器说明的完整列表。一个基本块可以以phi指令开始，但在一个基本块内，既不允许phi指令，也不允许分支指令。换句话说，只能在第一个指令中输入一个基本块，并且只能在最后一个指令中留下一个基本块，即结束指令。不可能在基本块内分支到指令，也不可能从基本块中间分支到另一个基本块。请注意，带有call指令的简单函数调用可以发生在基本块中。每个基本块只有一个标签，标记基本块的第一条指令，标签是分支指令的目标。可以将分支视为两个基本块之间的有向边，从而生成控制流图(CFG)。一个基本块可以有前身和后继，函数的第一个基本块是特殊的(因为它不允许有前块)。

由于这些限制，源语言中的控制语句，如WHILE和IF，会产生几个基本块。来看一下WHILE语句。WHILE语句的条件控制是执行循环体还是执行下一个语句，该条件语句必须在一个单独的基本块中生成，因为其两个前块:

\begin{itemize}
\item
由WHILE之前的语句产生的基本块

\item
从循环体的末端返回到条件的分支
\end{itemize}

还有两个后块:

\begin{itemize}
\item
循环体的开始部分

\item
由WHILE后面的语句产生的基本块
\end{itemize}

循环体本身至少有一个基本块:

\myGraphic{0.5}{content/part2/chapter4/images/1.png}{图4.1 - WHILE语句的基本块}

IR代码生成遵循这种结构。在CGProcedure类中存储一个指向当前基本块的指针，并使用llvm::IRBuilder<>的实例将指令插入基本块。创建基本块:

\begin{cpp}
void emitStmt(WhileStatement *Stmt) {
    llvm::BasicBlock *WhileCondBB = llvm::BasicBlock::Create(
        CGM.getLLVMCtx(), "while.cond", Fn);
    llvm::BasicBlock *WhileBodyBB = llvm::BasicBlock::Create(
        CGM.getLLVMCtx(), "while.body", Fn);
    llvm::BasicBlock *AfterWhileBB = llvm::BasicBlock::Create(
        CGM.getLLVMCtx(), "after.while", Fn);
\end{cpp}

Fn变量表示当前函数，getLLVMCtx()返回LLVM上下文，两者都会在稍后设定。我们用一个基本块的分支来结束当前的基本块，该分支将保存以下条件:

\begin{cpp}
    Builder.CreateBr(WhileCondBB);
\end{cpp}

该条件的基本块成为新的当前基本块。生成条件语句，并以一个条件分支结束代码块:

\begin{cpp}
    setCurr(WhileCondBB);
    llvm::Value *Cond = emitExpr(Stmt->getCond());
    Builder.CreateCondBr(Cond, WhileBodyBB, AfterWhileBB);
\end{cpp}

接下来，生成循环体，在条件语句的基本块中添加一个分支:

\begin{cpp}
    setCurr(WhileBodyBB);
    emit(Stmt->getWhileStmts());
    Builder.CreateBr(WhileCondBB);
\end{cpp}

这样，就生成了WHILE语句。现在已经生成了WhileCondBB和Curr块，可以对其进行密封:

\begin{cpp}
    sealBlock(WhileCondBB);
    sealBlock(Curr);
\end{cpp}

WHILE语句后面的空基本块变成了当前基本块:

\begin{cpp}
    setCurr(AfterWhileBB);
}
\end{cpp}

按照这个模式，可以为语言的每个语句创建emit()方法。

































